package airthmetic.exercise.arr;

public class _88_合并两个有序数组 {

    // 双指针 时间复杂度 O(m+n) 空间复杂度O(n)
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        // 定义一个拷贝数组
        int[] nums1_copy = new int[m];
        System.arraycopy(nums1, 0, nums1_copy, 0, m);

        int i = 0;
        int j = 0;
        int p = 0;

        while(i < m && j < n){
            nums1[p++] = nums1_copy[i] < nums2[j] ? nums1_copy[i++] : nums2[j++];
        }

        if (i < m){
            System.arraycopy(nums1_copy, i, nums1, p, m - i);
        }

        if (j < n){
            System.arraycopy(nums2, j, nums1, p, n - j);
        }
    }

    // 双指针 时间复杂度 O(m+n) 空间复杂度O(1)
    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int p = m + n - 1;

        while(i >= 0 && j >= 0){
            nums1[p--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
        }

        if (j >= 0){
            System.arraycopy(nums2, 0, nums1, 0, j + 1);
        }
    }


    public static void main(String[] args) {
//        int[] nums1 = new int[]{1,2,3,0,0,0};
//        int[] nums2 = new int[]{2,5,6};
//        int m = 3;
//        int n = 3;
//        merge(nums1,m,nums2,n);
//        for (int i : nums1) {
//            System.out.println(i);
//        }
//
//        int[] nums3 = new int[]{2,5,6,0,0,0};
//        int[] nums4 = new int[]{1,2,3};
//        merge2(nums3,m,nums4,n);
//        for (int i : nums3) {
//            System.out.println(i);
//        }




        int[] nums5 = new int[]{4,0,0,0,0,0};
        int[] nums6 = new int[]{1,2,3,5,6};
        int m3 = 1;
        int n3 = 5;

        merge3(nums5,m3,nums6,n3);
        for (int i : nums5) {
            System.out.println(i);
        }
    }

    private static void merge3(int[] nums1, int m, int[] nums2, int n) {
        int[] nums1_copy = new int[m];
        System.arraycopy(nums1,0, nums1_copy, 0,  m);

        int i = nums1_copy.length - 1;
        int j = nums2.length -1;
        int k = nums1.length -1;
        while(i>=0 && j>=0){
            if(nums1_copy[i] > nums2[j]){
                nums1[k--] = nums1_copy[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }
        if(j >=0){
            System.arraycopy(nums2,0,nums1,0, j + 1);
        }
    }
}
